package com.leetcode.动态规划;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7]
 * 的子序列。
 * 
 * @author LZF
 *
 */
public class L300最长递增子序列 {
	public static void main(String[] args) {
		int result = lengthOfLIS(new int[] {1,3,6,7,9,4,10,5,6});
		System.out.println(result);
	}
	
	/**
	 * dp[i]:表示以位置i为结尾的最长子序列的长度
	 * 则位置i的最长递增子序列等于（j从0到n-1的各个位置上的最长子序列加1）的最大值，前提是nums[i]>nums[j]
	 * 则递推公式为 if(nums[i]>nums[j]) dp[i] = max(dp[i],dp[j]+1)
	 * 初始化
	 * !!!整个dp初始化为1，因为最少的情况下，只有一个元素的长度
	 * 例如 nums=[1,2,3,4,10,6]，当在算dp[5],也就是nums[5]=6的时候
	 * 在j=3时,nums[5]>nums[3],此时dp[5]已经更新为最大值等于5了
	 * 即使j=4时，nums[5]>nums[4]不满足，没有更新dp[5]，但是dp[5]已经存了最大值
	 * 
	 * 由公示可以看到dp[i]并 不一定 受dp[i - 1]、dp[i - 2]等影响，因为只有满足if(nums[i] > nums[j])，才会被影响
	 * 因此需要在过程中保存dp[i]的最大值，将此结果返回。
	 * 例如nums={1,3,6,7,9,4,10,5,6}时，dp=[1, 2, 3, 4, 5, 3, 6, 4, 5]
	 * 因此我们需要在过程中保存dp的最大值6，将6返回
	 * @param nums
	 * @return
	 */
	public static int lengthOfLIS(int[] nums) {
		if(nums.length <= 1) return nums.length;
		int[] dp = new int[nums.length];
		Arrays.fill(dp,1);
		int result = 0;
		for(int i = 1;i < nums.length;i++) {
			for(int j = 0;j < i;j++) {
				if(nums[i] > nums[j])
					dp[i] = Math.max(dp[i],dp[j] + 1);
			}
			result = Math.max(result,dp[i]);
		}
		System.out.println(Arrays.toString(dp));
		return result;
	}
}
